package com.xiaoyu.binaryTree;

import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * @program: DS_and_A
 * @description: TODO
 * @author: YuWenYi
 * @create: 2021-05-20 16:23
 **/
public class PreorderTraversal_144 {

    /*
        前序遍历（迭代法）
        我们先看一下前序遍历。
        前序遍历是中左右，每次先处理的是中间节点，那么先将根节点放入栈中，然后将右孩子加入栈，再加入左孩子。
        为什么要先加入 右孩子，再加入左孩子呢？ 因为这样出栈的时候才是中左右的顺序。
    * */
    private List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new LinkedList<>();
        Deque<TreeNode> stack = new LinkedList<>();

        while (root != null || !stack.isEmpty()){
            if (root!=null){
                //先加头
                list.add(root.val);
                if (root.right != null){
                    stack.push(root.right);
                }
                root = root.left;
            }else {
                root = stack.pop();
            }
        }
        return list;
    }


    //递归写法2:这个写法可以快速改编成后续遍历
    public List<Integer> preorderTraversal2(TreeNode root) {
        Deque<TreeNode> stack = new LinkedList<>();
        LinkedList<Integer> list = new LinkedList<>();
        //边往下挖,边添加
        while (root!=null || !stack.isEmpty()){
            if (root != null){
                //每次前序遍历时，都将节点写入结果链表尾
                list.add(root.val);
                if (root.right != null){
                    stack.push(root.right);
                }
                //优先访问左结点
                root = root.left;
            }else {
                root = stack.pop();
            }
        }
        return list;
    }

    public static void main(String[] args) {
        PreorderTraversal_144 pt = new PreorderTraversal_144();

        TreeNode right = new TreeNode(3,new TreeNode(6),new TreeNode(7));
        TreeNode left = new TreeNode(2,new TreeNode(4),new TreeNode(5));
        TreeNode root = new TreeNode(1,left,right);

        System.out.println(pt.preorderTraversal2(root));
    }
}
